|
In the mathematical discipline of graph theory, a graph ''C'' is a covering graph of another graph ''G'' if there is a covering map from the vertex set of ''C'' to the vertex set of ''G''. A covering map ''f'' is a surjection and a local isomorphism: the neighbourhood of a ''v'' vertex in ''C'' is mapped bijectively onto the neighbourhood of ''f''(''v'') in ''G''. The term lift is often used synonymous for a covering graph of a connected graph. In graph theory, a covering graph may also refer to a subgraph that contains either all edges (edge cover) or all vertexes (vertex cover). The combinatorial formulation of covering graph is immediately generalized to the case of multigraph. If we identify a multigraph with a 1-dimensional cell complex, a covering graph is nothing but a special example of covering spaces of topological spaces, so that the terminology in the theory of covering spaces is available; say covering transformation group, universal covering, abelian covering, and maximal abelian covering. ==Definition== Let ''G'' = (''V'', ''E'') and ''C'' = (''V''2, ''E''2) be two graphs, and let ''f'': ''V''2 → ''V'' be a surjection. Then ''f'' is a ''covering map'' from ''C'' to ''G'' if for each ''v'' ∈ ''V''2, the restriction of ''f'' to the neighbourhood of ''v'' is a bijection onto the neighbourhood of ''f''(''v'') ∈ ''V'' in ''G''. Put otherwise, ''f'' maps edges incident to ''v'' one-to-one onto edges incident to ''f''(''v''). If there exists a covering map from ''C'' to ''G'', then ''C'' is a ''covering graph'', or a ''lift'', of ''G''. An ''h-lift'' is a lift such that the covering map ''f'' has the property that for every vertex ''v'' of ''G'', its ''fiber'' ''f−1(v)'' has exactly ''h'' elements. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「covering graph」の詳細全文を読む スポンサード リンク
|